专题七：查找

查找的内容包括以下几个部分：

首先要区分什么是静态查找和动态查找

静态查找：只进行查找和检索操作
动态查找：在查找的同时插入不存在的记录
顺序查找
分块查找
折半查找
二叉排序树查找
平衡二叉树（不考叭考也只考构造过程）如果想看的话红黑树其实也是平衡二叉树红黑树
B+树 B-树（期末考试也不考）
哈希表---包括构造哈希的方法和防止哈希碰撞的几种方法

顺序查找就不说了没啥好说的

折半查找：其实就是二分查找思路也不说了这里说一下代码：

而且其实二分查找有有三种因为有的是不严格递增的查左端点还是右端点的区别

int binarySearch(vector<int>& nums, int target) {
    int left = 0; 
    // 注意
    int right = nums.size() - 1;

    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            // 注意
            left = mid + 1;
        else if (nums[mid] > target)
            // 注意
            right = mid - 1;
    }
    return -1;
}

分块查找之前没有接触过：

分块查询实际上是一种结合了顺序查询和折半查找优点的查找技术

在分块查询中，数据被分成若干个“块”或者“桶”，每个块内的元素不必有序，但是块与块之间必须是有序的

适合动态的因为往里插入不用再排序

二叉排序树 ---- 中序遍历

查找代码
构建过程
构建代码

查找代码：

bool find(TreeNode root,int value){
	while(root!=nullptr){
		if(root->data==value)
			return true;
		if(root->data<value)
			root=root->right;
		if(root->data>value)
			root=root->left;
	}
	return false;
}

构建

TreeNode* insert(TreeNode* root,int value){
	while (temp != NULL) {
			if (val < temp->data) {  //如果要放入的值小于根节点
				if (temp->left == NULL) {  //根节点左孩为空，就直接放入
					temp->left = node;
					return;
				}
				else {
					temp = temp->left;  //根节点左孩不为空，就指向下一个左孩节点
				}
			}
			else {
				if (temp->right == NULL) { //右孩为空，直接放入
					temp->right = node;
					return;
				}
				else {
					temp = temp->right;  //右孩不为空，指向下一个右孩节点
				}
			}
		}
}

平衡二叉树生成过程左子树和右子树深度不超过1

构造4 5 7 2 1 3 6